COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00011 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a36.tex[154,phy] \today\hfill}

\bigskip
\line{\bf Primitive Roots.\hfill}

\proclaim Theorem. $\sum↓{e\mid d}\phi(e)=d$.\par

\noindent
{\bf Proof.} The number of proper fractions $0≤i/d<1$ that have denominator~$d$
is~$d$. After reducing each to lowest terms, all denominators are divisors
of~$d$. For each such 
divisor~$e$, there are all fractions $j/e$ with $0≤j/e<1$ and
$j$~prime to~$e$; there are $\phi(e)$ such~$j$, so another formula for the
number of fractions is $\sum↓{e\mid d}\phi(e)$.

\proclaim
Theorem.   Let $p$ be a prime and $de=p-1$; then $x↑d≡c\pmod{p}$
has solutions~$x$ iff $c$ is an $e↑{\rm th}$ root of unity. If it has
any solutions, it has exactly~$d$ of them. In particular, there are
exactly $d\;d↑{\rm th}$ roots of unity.\par

\noindent
{\bf Proof:} For all $i\not\equiv 0$, $1≡i↑{p-1}≡(i↑d)↑e$. That is to
say, there are $p-1$ roots~$i$ of $x↑{p-1}≡1$, and the $d↑{\rm th}$
powers $y=i↑d$ of those roots in turn satisfy $y↑e≡1$. There are at
most $e$~values of~$y$ satisfying $y↑e≡1$, and for each~$y$ there are
at most $d$~values of~$i$ satisfying $i↑d≡y$, giving at most the
$de=p-1$ values of $i\not\equiv 0$, possible only if there are exactly
$e$~roots of $y↑e≡1$, and each such~$y$ has exactly $d\;d↑{\rm th}$ roots.

Taking $e=2$, $d={p-1\over 2}$, for $p$ an odd prime, and $y=\pm 1$, we 
find there are exactly ${p-1\over 2}$ solutions to each of
$x↑{(p-1)/2}≡1$ and $x↑{(p-1)/2}≡-1$.

\medskip
{\rmn
{\narrower\smallskip\noindent
({\bf Paradigm:} prove summation identities by counting a set whole and
partitioned.) 

Example of the paradigm. Count the set of bit strings of length~$N$; there
are $2↑N$ of them. Partition by the number~$i$ of bits after the
first~1: There are~$2↑i$. There is also a string of all zeroes. This gives
$$\sum↓{i=0}↑{N-1}2↑i+1=2↑N\,.$$

\smallskip
Deeper example of the paradigm: Count the number of $(n+1)$-bit strings
in which there are $b+1$ one-bits; the formula is ${n+1\choose b+1}$. Count
those which have the last one-bit in position $i+1$; the formula
is ${i\choose b}$. Summing, $\sum↓{i=0}↑n{i\choose b}={n+1\choose b+1}$.
\smallskip}
}

\medskip
We say $a\not\equiv 0$ has order $n\!\!\!\!\!\pmod{p}$ if $n$ is the smallest
positive number for which $a↑n≡1$. Since $a↑{p-1}≡1$, every nonzero
number has an order. Since the powers $a↑i$ of $a$ restart at~1 whenever
$i$~is a multiple of~$n$, $a↑i≡1$ iff $n\mid i$. 

\proclaim
Theorem.  If $d\mid (p-1)$, there are exactly $\phi(d)$ numbers
of order $d\pmod{p}$. If not, there are none.\par

\noindent
{\bf Proof.} $x↑d≡1$ iff $x$ is of order~$i$, for some divisor~$i$ of~$d$.
Let $f(i)$ be the number of~$x$ of order~$i$. Since $x↑d≡1$ has exactly
$d$~solutions, $\sum↓{i\mid d}f(i)=d$. (The counting paradigm again.)
Recalling that $\sum↓{i\mid d}\phi(i)=d$, we see by
(course-of-values) induction on~$d$ that for $d\mid(p-1)$,
$f(d)=\phi(d)$. Because 1 is prime to~$d$, $\phi(d)>0$, and there
are roots of unity of every order that divides~$d$. In particular,
there are $\phi(p-1)$ {\it primitive roots\/}: roots of order $p-1$,
whose powers include all non-zero values.

\proclaim
Theorem.  If each $x↓i$ has order $e↓i$ ($1≤i≤n$), and the $e↓i$
are relatively prime, then $\prod x↓i$ has order $\prod e↓i$.\par

\noindent
{\bf Proof for $n=2$.} If $x↓1x↓2$ has order $j$, then $(x↓1x↓2)↑j≡1$,
and $1≡(x↓1x↓2)↑{je↓1}≡x↓1↑{e↓1j}x↓2↑{je↓1}=x↓2↑{je↓1}$,
$je↓1$~is a multiple of~$e↓2$, so $j$ is a multiple of~$e↓2$.
By symmetry, it is also a multiple of~$e↓1$, and therefore of~$e↓1e↓2$.
Conversely, $(x↓1x↓2)↑{e↓1e↓2}=x↓1↑{e↓1e↓2}x↓2↑{e↓2e↓1}≡1$.

\medskip\noindent
{\bf Proof for $n>2$.} Repeatedly apply the $n=2$ case to
$x↓1x↓2$, $x↓1x↓2x↓3$, $x↓1x↓2x↓3x↓4$, etc.

\medskip
So, to find a primitive ${\rm root}\pmod{p}$, where $p-1=\prod q↓e↑{e↓i}$,
it suffices to find values of order $q↓i↑{e↓i}$ for each~$i$ and
multiply them. If $r$ is selected at random, $r↑{(p-1)/q↓i}$ has
order $q↓i↑{e↓i}$ unless the exponent of~$q↓i$ in the order of~$r$
is less than~$e↓i$; the chance of this is only $1/q↓i$; so the expected 
number of
values of~$r$ that must be tested is ${1\over 1-(1/q↓i)}={q↓i\over q↓i-1}$.

Another way to find primitive roots is to take a random~$r$, and check
that $r↑{(p-1)/q}\not\equiv 0$ for each prime factor~$q$ of $p-1$. The chance
that $r$~will work is $\prod \bigl(1-{1\over q↓i}\bigr)$ over the
prime factors~$q↓i$ of $p-1$; for this chance to be as small as
0.1, $p$~must be greater than the product of all primes up to 271,
or $3.1666\times 10↑{110}$.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd
First draft (not published)
September 19, 1985.
%revised date;
%subsequently revised.

\bye